/**
* @file Dp.cpp in Leetcode
* @author rebeater
* @comment
* Create on 8/13/21 10:35 PM
* @version 1.0
**/



#include <iostream>
#include <cstring>
using namespace std;

/**
 * Dp for 0/1 pack
 * 0/1背包问题
 * 最优方程：
 * 				[  0  if i or w = 0;
 * OPT[i][w] = <  opt[i-1][w]   if wi 不能放进书包，即wi>c;
 * 				[ max{ opt[i-1][w](不放入),opt[i-1][w-wi]+vi(放入)}  if wi能放进书包
 * @param weights  物品重量
 * @param values 物品价值
 * @param len 物品数量
 * @param capacity 背包容量
 * @return 最大价值
 */
int BackPack01(const int weights[], const int values[], const int len, const int capacity) {
  int opt[len + 1][capacity + 1];
  int wi, vi;
  for (int i = 0; i <= capacity; i++) {
	opt[0][i] = 0;
  }
  for (int i = 0; i <= len; i++) {
	opt[i][0] = 0;
  }
  for (int i = 1; i <= len; i++) {
	for (int c = 1; c <= capacity; c++) {
	  wi = weights[i - 1];/*第i件物品*/
	  vi = values[i - 1];/*第i件物品*/
	  if (wi > c) {
		opt[i][c] = opt[i - 1][c];
	  } else {
		opt[i][c] = max(opt[i - 1][c - wi] + vi, opt[i - 1][c]);
	  }
	}
  }
  /*show opt table*/
  /* for (int i = 0; i <= len; i++) {
	 for (int j = 0; j <= capacity; j++) {
	   cout << opt[i][j] << " ";
	 }
	 cout << endl;
   }//*/
  return opt[len][capacity];
}
/**
 * @param weights  物品重量
 * @param values 物品价值
 * @param len 物品种类
 * @param capacity 背包容量
 * @return 最大价值
 */
int BackPackFull(const int weights[], const int values[], const int len, const int capacity) {
  int opt[len + 1][capacity + 1];
  int wi, vi;
  for (int i = 0; i <= capacity; i++) {
	opt[0][i] = 0;
  }
  for (int i = 0; i <= len; i++) {
	opt[i][0] = 0;
  }
  for (int i = 1; i <= len; i++) {
	for (int c = 1; c <= capacity; c++) {
	  wi = weights[i - 1];/*第i件物品*/
	  vi = values[i - 1];/*第i件物品*/
	  if (wi > c) {
		opt[i][c] = opt[i - 1][c];
	  } else {
		opt[i][c] = max(opt[i][c - wi] + vi, opt[i - 1][c]);
	  }
	}
  }
  /*show opt table*/
  for (int i = 0; i <= len; i++) {
	for (int j = 0; j <= capacity; j++) {
	  cout << opt[i][j] << " ";
	}
	cout << endl;
  }//*/
  return opt[len][capacity];
}

class SingleEdit {
 public:
  int operator()(char a, char b) {
	if (a == '-' or b == '-') {
	  return 1;/*删减操作*/
	}
	if (a == b) {
	  return 0;/*match*/
	} else {
	  return 1;/*替换操作*/
	}
  };
};

#include "string"
#define MIN2(x,y) (x<y?x:y)
//#define MIN3(x, y, z) x<y?(x<z?x:z):(y<z?y:(z<x?z:x))
#define MIN3(x, y, z) MIN2(x,MIN2(y,z))

/**
 * 动态规划求两个字符串之间的编辑距离
 * 定义损失函数对不match的状况给1，否则给0可以求编辑距离，反之可以求最长公共子序列。
 * @param str1
 * @param str2
 * @param s 损失函数,
 * @return
 */
int EditDistance(const string &str1, const string &str2,SingleEdit s=SingleEdit()) {
  int len1 = str1.size() + 1;
  int len2 = str2.size() + 1;
  int **opt = new int *[len1];
//  auto s = SingleEdit();
  /*为OPT表动态分配内存*/
  for (int i = 0; i < len1; i++) {
	opt[i] = new int[len2];
  };
  /*初始化OPT表*/
  for (int i = 0; i < len1; i++) {
	opt[i][0] = i;
  }
  for (int i = 0; i < len2; i++) {
	opt[0][i] = i;
  }
  for (int j = 1; j < len2; j++) {
	for (int i = 1; i < len1; i++) {
	  opt[i][j] = MIN3(opt[i - 1][j - 1] + s(str1[i - 1], str2[j - 1]),
					   opt[i - 1][j] + s(str1[i - 1], '-'),
					   opt[i][j - 1] + s('-', str2[j - 1])
				  );
	}
  }
  /*show opt table*/
  for (int i = 0; i < len1; i++) {
	for (int j = 0; j < len2; j++) {
	  cout << opt[i][j] << " ";
	}
	cout << endl;
  }//*/
  auto res = opt[len1 - 1][len2 - 1];
  for (int i = 0; i < len1; i++)delete[] opt[i];
  delete[] opt;
  return res;
}

int testBackPack() {
  int capacity = 6, len = 3, weights[] = {2, 2, 3}, values[] = {2, 2, 3};
  cout << BackPackFull(weights, values, len, capacity);
  return 0;
}

int main() {
//  SingleEdit s;
//  cout<<SingleEdit()(1,2);
  string s2 = "OCURRANCE";
  string s1 = "OCCURRENCE";
  cout << EditDistance(s2, s1);
}